r=black>Yahoo! is not affiliated with the authors of this page or responsible for its content.
Microsoft PowerPoint - GAMS_LGO [Read-Only] (C) Janos D. Pinter, PCS Inc.
Global Optimization
with GAMS/LGO
Introduction, Usage, and Applications
János D. Pintér
PCS Inc., Halifax, NS, Canada
INFORMS Annual Meeting
Atlanta, GA October 2003 (C) Janos D. Pinter, PCS Inc.
Introduction
Nonlinear processes and phenomena: NLP models in
the sciences, engineering, and economics
Nonlinear models frequently possess multiple optima:
hence, their solution requires a suitable global scope
search approach
The objective of global optimization is to find the
absolutely best solution of decision models, in the
possible presence of local (sub-)optima (C) Janos D. Pinter, PCS Inc.
Introduction
(continued)
Global optimization is a relatively new field: noticeable
interest and research efforts only since ~ 1970
Solid general theoretical foundations since ~ 1980: globally
convergent, exact deterministic and stochastic algorithms;
as well as a range of heuristic approaches
Availability of several gradually developed/improved,
professional level global optimization codes; in addition, a
significant variety of research codes since ~ 1990
Collaboration between the GAMS Corp. & the developers of
BARON, LGO, and OQNLP
GAMS/GO solvers (~ 2000) (C) Janos D. Pinter, PCS Inc.
Introduction
(continued)
Topics covered
Brief GAMS review
General GO model statement and related notes
LGO solver: current implementations
LGO solver: key features
GAMS/LGO implementation and usage
Illustrative numerical example(s)
Existing and prospective applications
Illustrative references (C) Janos D. Pinter, PCS Inc.
GAMS (General Algebraic
Modeling System)
GAMS: development started as a research project at the
World Bank (1976); GAMS Devpt. Corp. (1988)
GAMS book by Brooke, Kendrick & Meeraus (1988);
subsequent revisions; currently, extensive further
documentation is available: papers, technical reports,
lectures, model libraries, web sites
GAMS: integrates core model development/parser system
and a range of connected solver options
10,000+ users in over 100 countries (2003) (C) Janos D. Pinter, PCS Inc. (C) Janos D. Pinter, PCS Inc.
GAMS Solver Options
(October 2003)
(C) Janos D. Pinter, PCS Inc.
GAMS NL Solvers
Nonlinear modeling capabilities have been available in
GAMS from the beginning
Some 3000 licensed GAMS systems are equipped with
NLP solver capability + educational users significant potential interest in GO solvers
Availability of
local NL
solvers (2003): NLP (MINOS,
CONOPT, SNOPT, LSGRG, PATHNLP, MOSEK,
TRAMP) and
MINLP
solvers (DICOPT, SBB)
Implementation of a range of algorithms and methods
(B&B, GRG, OA, SLP, SQP,) improves the overall
reliability of nonlinear modeling and solution efforts,
to
the benefit of modelers/users (C) Janos D. Pinter, PCS Inc.
GAMS Global Solvers
Available solvers:
BARON
Branch-and-reduce solver system
by The Optimization Firm
LGO
Global/nonlinear optimization solver suite
by PCS
OQNLP
OptQuest/NLP solver system
by OptTek Systems and Optimal Methods
Key differences between the global solver options:
underlying algorithms
external solver needs
optimality guarantees provided
model forms they can handle
model sizes they can handle (C) Janos D. Pinter, PCS Inc.
GAMS Global Solvers
(continued)
All solvers benefit from GAMS system services:
Search algorithms often have difficulties with equalities:
(automatic) defining equation elimination by GAMS
Dual solution unavailable, approximate solution only:
optional polishing call (CONOPT or other local solvers)
from solution found by global solver
Currently, no MINLP capability (in LGO):
B&B code SBB can make use of GAMS NLP sub-solvers
Seamless exchange of solvers is supported: for example,
setting
option nlp=lgo
activates LGO
Other benefits: benchmarking (model libraries such as
GlobalLib, PAVER), model converter utility, additional
model examples, documentation & technical notes (C) Janos D. Pinter, PCS Inc.
min f(x)
f: R
n
R
1
g(x)
0
g: R
n
R
m
x
l
x x
u
x, x
l
, x
u
, (x
l
< x
u
) are real n-vectors
Minimal analytical assumptions:
x
l
, x
u
finite
feasible set D={x
l
x x
u
: g(x)
0} non-empty
f, g continuous
These guarantee the existence of global solution set X*
Typically, we assume that X* is finite (at most, countable)
CGO covers a very general class of models, including all
combinatorial and mixed integer (MIP) problems
Continuous GO Model (C) Janos D. Pinter, PCS Inc.
GO models can be arbitrarily difficult to solve,
even in (very) low dimensions
200
400
600
800
1000
-1000
-500
500
1000
f(x)=x·sin( x)
0 x 1000
Illustrative GO Model, n=1 (C) Janos D. Pinter, PCS Inc.
-4
-2
0
2
4
-4
-2
0
2
-1
0
1
2
-4
-2
0
2
4
Numerical difficulty may increase exponentially,
as model size (n, m) grows
Illustrative GO Model, n=2 (C) Janos D. Pinter, PCS Inc.
Practical objective: solution estimates, on the basis of finite
sequences of search points and corresponding function values
{x
1
,,x
k
}, {f
1
,,f
k
}, {g
1
,,g
k
} (Note: higher order information, as
a rule, has no general value in the context of global search)
If the functions f and g are Lipschitz-continuous, then - based
on the sample sequence - deterministic lower/upper bounds
can be derived; hence, a rigorous convergence theory can be
developed
(|h(x
1
)-h(x
2
)|
L||x
1
-x
2
|| for x
1
,x
2
D; L=L(D,h) 0)
If the model functions are only continuous, then stochastic
convergence is the best one can aim for - and it can be properly
established
Implementation issues and challenges:
only a few details
Solving GO Models (C) Janos D. Pinter, PCS Inc.
The LGO (Lipschitz Global Optimizer) solver suite has been
designed and developed with GO models in mind that do not -
or may not - have an easily identifiable and exploitable
special structure
This scope specifically includes black box models, and
models with computable (perhaps non-analytical) functions:
examples will be shown and listed later on
Note that more structured GO models - e.g. with convex,
concave or indefinite QP objectives over convex domains -
also belong to the scope of LGO (as a rule, with a relatively
small performance hit - due to its broad-minded global
search methods, followed by classical local searches)
LGO Solver Suite: General Scope (C) Janos D. Pinter, PCS Inc.
LGO integrates several global search algorithms
adaptive partition and search (branch-and-bound)
adaptive random search
adaptive multi-start
heuristic (continuous) scatter search
and traditional local optimization methods
exact penalty method, box-constrained local search
generalized reduced gradient method
This approach flexibly supports the search for global or
local solutions in optimization models defined by continuous
(or Lipschitz) functions, w/o further necessary analytical
conditions
LGO Solver Suite: Components (C) Janos D. Pinter, PCS Inc.
No external solver needs; combinations with local solvers
are possible, and easy to add
Optimality guarantees provided: exact and stochastic
(deterministic, if model Lipschitz constants are known or can
be properly over-estimated during optimization)
Model forms handled: arbitrary continuous model functions
Model sizes: in principle, arbitrary (depending on processor
and RAM), but: curse of dimensionality... typical current
delivery versions: thousand(s) of variables and constraints
Customized versions of LGO implemented for several
major modeling platforms; used in advanced scientific,
engineering, and economic applications for over a decade
LGO Solver Suite:
Characteristics and Implementations (C) Janos D. Pinter, PCS Inc.
LGO silent version with a text I/O interface (compiler-
based; with Fortran, C, Delphi, API,... connectivity)
LGO IDE, with a Windows interface (as above)
LGO solver engine for Excel (PSP solver family)
LGO external solver link to Mathematica (MathOptimizer
Professional)
Further similar development in progress
LGO Solver Implementations
(continued) (C) Janos D. Pinter, PCS Inc. (C) Janos D. Pinter, PCS Inc.
MathOptimizer and MathOptimizer Professional
Software review in Scientific Computing World (July - August 2003) (C) Janos D. Pinter, PCS Inc. (C) Janos D. Pinter, PCS Inc.
GAMS/LGO Solver Operations
GAMS Model
Model description/preprocessing GAMS/LGO
Solver options
Solution report
LGO Solver Suite
Global search methods
for multiextremal models
Local search methods
for convex nonlinear models
Optional calls to other GAMS solvers
and to external program systems (C) Janos D. Pinter, PCS Inc. (C) Janos D. Pinter, PCS Inc. (C) Janos D